package com.cjm.algorithm.babo;

import com.cjm.algorithm.GeneratorUtils;
import com.cjm.algorithm.HelpUtils;

/**
 * 首先在末排序序列中找到最小(大)元素, 存放到排序序列的起始位置, 然后, 再从剩余末排序
 * 元素中继续寻找最小(大)元素, 然后放到已排序序列的末尾, 以此类推, 直到所有元素均排序完毕.
 */
public class SelectSort {
    public static void selectSort() {
        System.out.println("选择排序\r\n");
        int[] arr = GeneratorUtils.generator();
        selectSort(arr);
        GeneratorUtils.print(arr);
    }
    public static int[] selectSort(int[] arr) {
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            int inde = i;
            for(int j = i + 1; j < length;j++) {
                if (arr[j]< arr[inde]) {
                    inde = j;
                }
            }
            if (inde != i) {
                GeneratorUtils.swap(arr, inde, i);
            }
        }
        return arr;
    }

    public static void sort(int[] arr) {
        int l = 0,r = arr.length - 1;
        while (l < r) {
            int mi = l;
            int ma = r;
            if (arr[mi] > arr[ma] ) {
                HelpUtils.swap(arr, mi, ma);
            }

            for(int i = l+1;i<r;i++) {
                if (arr[i] < arr[mi] ) {
                    mi = i;
                } else if (arr[i] > arr[ma]) {
                    ma = i;
                }
            }

            HelpUtils.swap(arr, mi, l);
            HelpUtils.swap(arr, r, ma);

            l++;
            r--;
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            int[] generator = GeneratorUtils.generator(100, 0, 100);
            sort(generator);
            GeneratorUtils.print(generator);
        }
    }
}
